#include <iostream>

using namespace std;

// 143. 重排链表
// https://leetcode.cn/problems/reorder-list/description/

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode *middleNode(ListNode *head)
    {
        if (head->next == nullptr)
        {
            return head;
        }
        ListNode *pre = head;
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast != nullptr && fast->next != nullptr)
        {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        return slow;
    }
    ListNode *reverseList(ListNode *head)
    {
        ListNode *curNode = head;
        ListNode *pre = nullptr;
        ListNode *last = nullptr;
        while (curNode != nullptr)
        {
            last = curNode->next;
            curNode->next = pre;
            pre = curNode;
            curNode = last;
        }
        return pre;
    }
    void reorderList(ListNode *head)
    {
        if(head->next == nullptr){
            return ;
        }
        ListNode *middle = middleNode(head);
        ListNode *last = reverseList(middle);
        
        ListNode *headNext = nullptr;
        ListNode *lastNext = nullptr;
        while (head != nullptr && last != nullptr)
        {
            headNext = head->next;
            lastNext = last->next;
            head->next = last;
            if(headNext == nullptr){
                break;
            }
            last->next = headNext;
            

            head = headNext;
            last = lastNext;
        }

    }
};

int main()
{
    return 0;
}